package leetcode.code0352;

import java.util.TreeMap;

import leetcode.helper.HelpDebug;

public class SummaryRanges extends Solution352 {

	private TreeMap<Integer, Integer> tm;// TreeMap<区间开始,区间结束>

	public SummaryRanges() {
		tm = new TreeMap<>();
	}

	public void addNum(int val) {
		Integer floor = tm.floorKey(val);// 小
		Integer floorEnd = floor != null ? tm.get(floor) : null;// 小结尾
		Integer ceil = tm.ceilingKey(val);// 大
		Integer ceilEnd = ceil != null ? tm.get(ceil) : null;// 大结尾
		if (ceil != null && floor != null) {// 有大有小
			if (floorEnd + 1 == val && val + 1 == ceil) {// 将两个连一起
				tm.put(floor, ceilEnd);
				tm.remove(ceil);
			} else if (floorEnd + 1 == val) {// 同小的连一起,变成小的尾巴
				tm.put(floor, val);
			} else if (val + 1 == ceil) {// 同大的连一起,变成大的头
				tm.put(val, ceilEnd);
				tm.remove(ceil);
			} else if (val > floorEnd + 1 && val < ceil - 1) {
				tm.put(val, val);// 位于两者之间
			}
		} else if (ceil != null) {// 只有大
			if (val + 1 == ceil) {
				tm.put(val, ceilEnd);// 变成大的头
				tm.remove(ceil);
			} else if (val < ceil - 1) {
				tm.put(val, val);// 单独
			}
		} else if (floor != null) {// 只有小
			if (floorEnd + 1 == val) {// 变成小的尾
				tm.put(floor, val);
			} else if (val > floorEnd + 1) {
				tm.put(val, val);// 单独
			}
		} else {
			tm.put(val, val);// 就自己
		}

	}

	public int[][] getIntervals() {
		int size = tm.size();
		int[][] ans = new int[size][2];
		int p = 0;
		for (Integer start : tm.keySet()) {
			ans[p][0] = start;
			ans[p++][1] = tm.get(start);
		}
		return ans;
	}

	public static void main(String[] args) {
		int[][] ans = null;

		// ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"]
		// [[],[6],[],[6],[],[0],[],[4],[],[8],[],[7],[],[6],[],[4],[],[7],[],[5],[]]
		//
		// [null,null,[[6,6]],
		// null,[[6,6]],null,[[0,0],[6,6]],null,[[0,0],[4,4],[6,6]],
		// null,[[0,0],[4,4],[6,6],[8,8]],null,[[0,0],[4,4],[6,8]],
		// null,[[0,0],[4,4],[6,8]],null,[[0,0],[4,4],[6,8]],
		// null,[[0,0],[4,4],[6,8]],null,[[0,0],[4,8]]]
		SummaryRanges summaryRanges = new SummaryRanges();
		summaryRanges.addNum(6); // arr = [1]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 1]]
		HelpDebug.print(ans);
		summaryRanges.addNum(6); // arr = [1, 3]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
		HelpDebug.print(ans);
		summaryRanges.addNum(0); // arr = [1, 3, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(4); // arr = [1, 2, 3, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(8); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(7); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(4); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(7); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
		summaryRanges.addNum(5); // arr = [1, 2, 3, 6, 7]
		ans = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
		HelpDebug.print(ans);
	}

}
